package chart;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author yezh
 * @date 2024/9/14 17:53
 */
public class IsCompleteTree {

    public static boolean isCompleteTree(TreeNode<Integer> root) {
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        // 是否已经出现过 叶子结点 or 只有左子树的结点, 出现这种结点后, 后续结点必须都是叶子结点
        boolean isLeaveOrLeft = false;
        while (!q.isEmpty()) {
            root = q.poll();
            if (isLeaveOrLeft) {
                if (root.left != null || root.right != null) return false;
            } else {
                if (root.left != null && root.right != null) {
                    q.offer(root.left);
                    q.offer(root.right);
                } else if (root.right != null) return false;
                else isLeaveOrLeft = true;
            }
        }
        return true;
    }

}
